1059E - Split the Tree - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
int n, l, w[MAXN], f[MAXN][25], dep[MAXN], rch[MAXN], mrch[MAXN];
int ans = 0;
vector<int> to[MAXN];
long long depw[MAXN], s;
void build (int cur) {
	dep[cur] = dep[f[cur][0]] + 1;
	depw[cur] = depw[f[cur][0]] + w[cur];
	for (int i = 1;i <= 20;i++) f[cur][i] = f[f[cur][i - 1]][i - 1];
	for (int p: to[cur]) {
		build (p);
	}
}
void solve (int x) {
	int mi = 0x3f3f3f3f;
	for (int p: to[x]) {
		solve (p);
		mi = min (mi, mrch[p]);
	}
	if (mi <= dep[x]) mrch[x] = mi;
	else {
		mrch[x] = rch[x];
		ans++;
	}
}
int main () {
	ios::sync_with_stdio (false);
	cin.tie (0);
	cin >> n >> l >> s;
	for (int i = 1;i <= n;i++) {
		cin >> w[i];
		if (w[i] > s) {
			cout << "-1" << endl;
			return 0;
		}
	}
	for (int i = 2;i <= n;i++) {
		cin >> f[i][0];
		to[f[i][0]].push_back (i);
	}
	build (1);
	for (int i = 1;i <= n;i++) {
		long long wt = s;
		int x = i, res = 0;
		for (int j = 20;j >= 0;j--) {
			if (depw[i] - depw[f[f[x][j]][0]] <= wt) {
				x = f[x][j];
				res += 1 << j;
			}
		}
		res = min (res, l - 1);
		rch[i] = dep[i] - res;
//		cout << i << " can reach " << rch[i] << endl;
	}
	solve (1);
	cout << ans << endl;
	return 0;
}